215. Kth Largest Element in an Array

문제

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

You must solve it in O(n) time complexity.

예제 입출력

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

참고

You can read the full description here.

힙 개념

요소 삽입

요소 추출

구현 코드

class BinaryHeap(object) :

    def __init__(self) :
        self.items = [None]

    def __len__(self) :
        return len(self.items)-1

    # 삽입 시 실행, 반복 구조 구현
    def _percolate_up(self) :
        i = len(self)
        parent = i // 2
        while parent > 0 :
            if self.items[i] < self.items[parent] :
                self.items[parent] , self.items[i] = \
                self.items[i] , self.items[parent]
            i = parent
            parent = i // 2
    def insert(self,k) :
        self.items.append(k)
        self._percolate_up()

    # 추출시 실행, 재귀 구조 구현
    def _percolate_down(self,idx) :
        left = idx * 2
        right = idx * 2 + 1
        smallest = idx

        if left <= len(self) and self.items[left] < self.items[smallest] :
            smallest = left

        if right <= len(self) and self.items[right] < self.items[smallest] :
            smallest = right

        if smallest != idx :
            self.items[idx] , self.items[smallest] = \
            self.items[smallest] , self.items[idx]
            self._percolate_down(smallest)

    def extract(self) :
        extracted = self.items[1]
        self.items[1] = self.items[len(self)]
        self.items.pop()
        self._percolate_down(1)
        return extracted

풀이 1

접근법

1. 리스트를 heap으로 만들고 해당 번째까지 뽑아줍니다.

구현 코드

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        result = 0
        n = len(nums) - (k - 1)

        while n > 0:
            result = heapq.heappop(nums)
            n -= 1

        return result

복잡도 분석

• $n$: 노드의 수
• 시간복잡도: $O(n)$

---

책에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 2

접근법

1. 새로운 힙을 만들어 heappush, heappop 합니다.
2. 최대 힙을 만들기 위해 음수로 저장하고 음수로 출력합니다.

구현 코드

import heapq
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = list()
        for n in nums:
            heapq.heappush(heap, -n)

        for _ in range(1, k):
            heapq.heappop(heap)

        return -heapq.heappop(heap)

풀이 3

접근법

1. heapify로 힙으로 바꿔줍니다.
2. 최소 힙이기 때문에 k번이 아닌 len(nums) - k + 1 번을 뽑습니다.

구현 코드

import heapq
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)

        for _ in range(len(nums) - k):
            heapq.heappop(nums)

        return heapq.heappop(nums)

풀이 4

접근법

1. 정렬을 이용합니다.

구현 코드

from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums, reverse=True)[k - 1]